package com.hanxiaozhang.link;

import java.util.HashMap;

/**
 * 〈一句话功能简述〉<br>
 * 〈一种特殊的单链表节点类描述如下{@link Node}。
 * rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，
 * 也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点head，
 * 请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
 * 【要求】时间复杂度O(N)，额外空间复杂度O(1) 〉
 *
 * @author hanxinghua
 * @create 2021/10/24
 * @since 1.0.0
 */
public class CopyListWithRandom {


    public static void main(String[] args) {
        Node head = null;
        Node res1 = null;
        Node res2 = null;
        printRandLinkedList(head);
        res1 = copyListWithRand1(head);
        printRandLinkedList(res1);
        res2 = copyListWithRand2(head);
        printRandLinkedList(res2);
        printRandLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        head.next.next.next.next.next = new Node(6);

        // 1 -> 6
        head.rand = head.next.next.next.next.next;
        // 2 -> 6
        head.next.rand = head.next.next.next.next.next;
        // 3 -> 5
        head.next.next.rand = head.next.next.next.next;
        // 4 -> 3
        head.next.next.next.rand = head.next.next;
        // 5 -> null
        head.next.next.next.next.rand = null;
        // 6 -> 4
        head.next.next.next.next.next.rand = head.next.next.next;

        printRandLinkedList(head);
        res1 = copyListWithRand1(head);
        printRandLinkedList(res1);
        res2 = copyListWithRand2(head);
        printRandLinkedList(res2);
        printRandLinkedList(head);
        System.out.println("=========================");

    }

    /**
     * 方法1
     * 1) 创建一个Map存储<节点，复制节点>的关系
     * 2) 处理复制节点的next和rand指针
     *
     * @param head
     * @return
     */
    public static Node copyListWithRand1(Node head) {
        //  创建一个Map，并循环赋值
        HashMap<Node, Node> map = new HashMap<>(16);
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.value));
            cur = cur.next;
        }
        // 处理复制节点的next、rand指针
        cur = head;
        while (cur != null) {
            // cur --> 源
            // map.get(cur) --> 复制节点
            // map.get(cur).next --> 复制节点的next节点
            // 复制节点的next节点 赋值 map.get(cur.next)
            map.get(cur).next = map.get(cur.next);
            map.get(cur).rand = map.get(cur.rand);
            cur = cur.next;
        }
        // 返回  map.get(head)
        return map.get(head);
    }

    /**
     * 方法2
     *
     * @param head
     * @return
     */
    public static Node copyListWithRand2(Node head) {
        if (head == null) {
            return null;
        }
        Node current = head;
        Node next = null;
        // 复制节点并链接到每个节点
        // 1 -> 2
        // 1 -> 1' -> 2  -> 2'
        while (current != null) {
            // current的下一个节点
            next = current.next;
            // 增加新创建节点
            current.next = new Node(current.value);
            // 连接老节点
            current.next.next = next;
            // 处理下一个节点
            current = next;
        }
        current = head;
        Node curCopy = null;
        // 设置复制节点的rand
        // 1 -> 1' -> 2 -> 2'
        while (current != null) {
            // current -> 老节点  current.next.next -> 老节点的下一个节点
            next = current.next.next;
            // current.next  -> 复制节点
            curCopy = current.next;
            // current.rand != null -> current.rand.next
            // current.rand == null -> null
            curCopy.rand = current.rand != null ? current.rand.next : null;
            // 处理下一个节点
            current = next;
        }
        Node res = head.next;
        current = head;
        // 恢复老链表，设置复制节点的next，并且将新老分割
        while (current != null) {
            next = current.next.next;
            curCopy = current.next;
            // 恢复老链表
            current.next = next;
            // 处理新节点next
            curCopy.next = next != null ? next.next : null;
            current = next;
        }
        return res;
    }


    private static class Node {
        public int value;
        public Node next;
        public Node rand;

        public Node(int data) {
            this.value = data;
        }
    }


    private static void printRandLinkedList(Node head) {
        Node cur = head;
        System.out.print("order: ");
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
        cur = head;
        System.out.print("rand:  ");
        while (cur != null) {
            System.out.print(cur.rand == null ? "- " : cur.rand.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }

}
